/**
 * 
 */
package hopcroft;

import helpers.AutomataOperations;
import helpers.HandleHashSet;
import helpers.Partitions;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Stack;


import automaton.DFA;

/**
 * @author LE VAN LINH
 *
 */
public class Hopcroft_Algorithm {

	/**
	 * Implements the Hopcoft's algorithm
	 * @param automata
	 * @return
	 */
	public static HashSet<HandleHashSet> hopCroft(DFA automata){
		HashSet<HandleHashSet> firstPart = Partitions.initial(automata);
		Stack<Splitter> waitingSet = new Stack<Splitter>();
		HandleHashSet minimalSet = Partitions.minimalSet(firstPart);
		
		// initialization of the waiting set
		for (String label : AutomataOperations.getLabels(automata)) {
			waitingSet.push(new Splitter(minimalSet, label));
		}
		
		while(!waitingSet.isEmpty()){
			Splitter spl = waitingSet.pop();
			
			HandleHashSet splitterStates = AutomataOperations.getSplitStates(automata, spl.getLetter(), spl.getSetP());
			Iterator<HandleHashSet> iterator = firstPart.iterator();
			while(iterator.hasNext()){
				HandleHashSet hset = iterator.next();
				HandleHashSet inter = HandleHashSet.interSection(hset, splitterStates);
				HandleHashSet subtract = HandleHashSet.subtraction(hset, splitterStates);
				if( inter.size() != 0 && subtract.size() !=0){
					
					firstPart.remove(hset);
					firstPart.add(inter);
					firstPart.add(subtract);
					iterator = firstPart.iterator();
					for(String lbl: AutomataOperations.getLabels(automata)){
						Splitter ss = new Splitter(hset, lbl);
						if(waitingSet.contains(ss)){
							waitingSet.remove(ss);
							waitingSet.push(new Splitter(inter, lbl));
							waitingSet.push(new Splitter(subtract, lbl));
						}
						else{
							waitingSet.push(new Splitter(HandleHashSet.minimalSet(inter, subtract), lbl));
						}						
					}										
				}
			}		
		}
		return firstPart;
	}
	
}
